package dp;

import java.util.ArrayList;
import java.util.List;

public class P213 {
    public int rob(int[] nums) {
        List<Integer> maxList = new ArrayList();
        backTrack(nums, 0, new ArrayList(), 0, maxList);
        return maxList.stream().max((a, b) -> a - b).get();
    }

    /**
     * @param nums
     * @param start   当前需要访问的位置， 还未访问
     * @param saved   已经访问过的节点集合
     * @param total   历史总和
     * @param maxList
     */
    void backTrack(int[] nums, int start, List<Integer> saved, int total, List<Integer> maxList) {
        if (start == nums.length - 1) { //访问到最后一个节点
            System.out.println(saved);
            if (saved.get(saved.size() - 1) == 1) { //不能选
                maxList.add(total);
            } else if (saved.get(0) == 0) { //选
                maxList.add(total + nums[start]);
            } else {
                maxList.add(total);
            }
        } else {
            //选
            if (start == 0 || saved.get(saved.size() - 1) == 0) {//第一个节点或上一个节点没有访问过
                int num = nums[start];
                saved.add(1);
                backTrack(nums, start + 1, saved, total + num, maxList);
                saved.remove(saved.size() - 1);
            }
            // 不选
            saved.add(0);
            backTrack(nums, start + 1, saved, total, maxList);
            saved.remove(saved.size() - 1);
        }
    }

    public static void main(String[] args) {
        int rob = new P213().rob(new int[]{94,40,49,65,21,21,106,80,92,81,679,4,61,6,237,12,72,74,29,95,265,35,47,1,61,397,52,72,37,51,1,81,45,435,7,36,57,86,81,72});
        System.out.println(rob);
    }
}
